'use strict'
var __ = require('lodash')

const MAX_MOVE_DIRECTION = 4;
const MAX_WARRIOR_TYPE = 5;
const HRD_GAME_ROW = 5;
const HRD_GAME_COL = 4;
const HRD_BOARD_WIDTH = 6;
const HRD_BOARD_HEIGHT = 7;
const BOARD_CELL_EMPTY = 0;
const BOARD_CELL_BORDER = -1;
const CAO_ESCAPE_LEFT = 1;
const CAO_ESCAPE_TOP = 3;

const WARRIOR_TYPE = {
    HT_BLOCK : 1,  //1x1
    HT_VBAR : 2,   //1x2
    HT_HBAR : 3,   //2x1
    HT_BOX : 4     //2x2
}

const DIRECTION = [ [0, -1], [1, 0], [0, 1], [-1, 0] ]

class MoveAction{
    constructor(heroIdx, dirIdx){
        this.heroIdx = heroIdx || 0
        this.dirIdx = dirIdx  || 0
    }
}

class Warrior {
    constructor(type, left, top){
        this.type = type
        this.left = left
        this.top = top
    }
}

class HrdGame{
    constructor(caoIdx, heroes){
        this.caoIdx = caoIdx;
        var startState = new HrdGameState();
        startState.initState(heroes)
        this.states = []
        this.zhash = {}
        this.result = 0;
        addNewStatePattern(this,startState)
    }
}

class HrdGameState {
    constructor(){
        this.board = []
        for(let i = 0; i<HRD_BOARD_HEIGHT; i++){
            this.board.push([])
            for(let j=0; j<HRD_BOARD_WIDTH; j++){
                this.board[i].push([])
                if(i==0 || j==0 || i==HRD_BOARD_HEIGHT-1 || j==HRD_BOARD_WIDTH-1){
                    this.board[i][j] = BOARD_CELL_BORDER
                }else{
                    this.board[i][j] = BOARD_CELL_EMPTY
                }
            }
        }
        this.parent = null;
        this.step = 0;
        this.move = new MoveAction()
        this.heroes = []
    }
    initState(heroes){
        for(let i = 0; i < heroes.length; i++)
        {
            if(!addGameStateHero(this, i, heroes[i]))
             {
                return false;
             }
        }
        return true;
    }
}

class Zobrist{
    constructor(){
        this.zobHash = []
        for(let i = 0; i < HRD_GAME_ROW; i++)
        {
            this.zobHash.push([])
            for(let j = 0; j < HRD_GAME_COL; j++)
            {
                this.zobHash[i].push([])
                for(let k = 0; k < MAX_WARRIOR_TYPE; k++)
                {
                    do{
                        var tmp = Math.random()
                        tmp = Math.floor(tmp * Math.pow(2,31))
                    }while(!tmp)
                    this.zobHash[i][j].push(tmp)
                }
            }
        }
    }
    set(hash,i,j,k){
        this.zobHash[i][j][k] = hash
    }
    get(i,j,k){
        return this.zobHash[i][j][k]
    }
}

var zobHash = new Zobrist()

function trySearchHeroNewState(game, gameState, heroIdx, dirIdx)
{
    let newState = moveHeroToNewState(gameState, heroIdx, dirIdx);
    if(newState) {
        if(addNewStatePattern(game, newState))
        {
             /*尝试连续移动，根据华容道游戏规则，连续的移动也只算一步*/
            tryHeroContinueMove(game, newState, heroIdx, dirIdx);
            return;
        }
    }
}

function searchNewGameStates(game, gameState)
{
    for(let i = 0; i < gameState.heroes.length; i++)
    {
        for(let j = 0; j < MAX_MOVE_DIRECTION; j++)
        {
            trySearchHeroNewState(game, gameState, i, j);
        }
    }
}

function resolveGame(game)
{
    let index = 0;
    while(index < game.states.length)
    {
        gameState = game.states[index];
        // if(gameState.heroes[game.caoIdx-1].top>1 && gameState.heroes[game.caoIdx-1].left==1){
        // console.log('length:'+game.states.length+' index:'+index+' cao:'+gameState.heroes[game.caoIdx-1].top+','+gameState.heroes[game.caoIdx-1].left)
        // console.dir(gameState.board)
        // }
        if(isEscaped(game, gameState))
        {
            game.result++;
            console.log('result:'+game.result+' step--'+gameState.step+' index:'+index)
            // break;
        }
        else
        {
            searchNewGameStates(game, gameState);
        }

        index++;
    }

    return (game.result > 0);
}

function addNewStatePattern(game, gameState)
{
    var l2rHash = getZobristHash(zobHash, gameState);
    if(!game.zhash[l2rHash])
    {
        game.zhash[l2rHash] = l2rHash;
        var r2lHash = getMirrorZobristHash(zobHash, gameState);
        game.zhash[r2lHash] = r2lHash;
        game.states.push(gameState);

        return true;
    }

    return false;
}

function isReverseDirection(dirIdx1, dirIdx2) {                     //编号相关为2的是对立方向
    return ( ((dirIdx1 + 2) % MAX_MOVE_DIRECTION) == dirIdx2);
}

function tryHeroContinueMove(game, gameState, heroIdx, lastDirIdx) {
    let d = 0;
    for(d = 0; d < MAX_MOVE_DIRECTION; d++)             //向四个方向试探移动
    {
        if(!isReverseDirection(d, lastDirIdx)){         //不向原方向移动
            let newState = moveHeroToNewState(gameState, heroIdx, d);
            if(newState)
            {
                if(addNewStatePattern(game, newState))
                {
                    newState.step--;
                }
                return;                                 //连续移动只能朝一个方向移动一次
            }
        }
    }
}

function moveHeroToNewState(gameState, heroIdx, dirIdx)
{
    if(canHeroMove(gameState, heroIdx, dirIdx))
    {
        var newState = new HrdGameState();
        if(newState)
        {
            copyGameState(gameState, newState);
            var hero = newState.heroes[heroIdx];
            const dir = DIRECTION[dirIdx];

            clearPosition(newState, hero.type, hero.left, hero.top);
            takePosition(newState, heroIdx, hero.type, hero.left + dir[0], hero.top + dir[1]);
            hero.left = hero.left + dir[0];
            hero.top = hero.top + dir[1];

            newState.step = gameState.step + 1;
            newState.parent = gameState;
            newState.move.heroIdx = heroIdx;
            newState.move.dirIdx = dirIdx;
            return newState;
        }
    }
    return null;
}

function copyGameState(from, to){
    to.board = __.cloneDeep(from.board)
    to.heroes = __.cloneDeep(from.heroes)
}

function canHeroMove(gameState, heroIdx, dirIdx)
{
    let cv1,cv2,cv3,cv4;
    let canMove = false;
    const hero = gameState.heroes[heroIdx];
    const dir = DIRECTION[dirIdx];

    switch(hero.type)
    {
    case WARRIOR_TYPE.HT_BLOCK:
        canMove = (gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 1] == BOARD_CELL_EMPTY);
        break;
    case WARRIOR_TYPE.HT_VBAR:
        cv1 = gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 1];
        cv2 = gameState.board[hero.top + dir[1] + 2][hero.left + dir[0] + 1];
        canMove = (cv1 == BOARD_CELL_EMPTY || cv1 == heroIdx + 1) && (cv2 == BOARD_CELL_EMPTY || cv2 == heroIdx + 1);
        break;
    case WARRIOR_TYPE.HT_HBAR:
        cv1 = gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 1];
        cv2 = gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 2];
        canMove = (cv1 == BOARD_CELL_EMPTY || cv1 == heroIdx + 1) && (cv2 == BOARD_CELL_EMPTY || cv2 == heroIdx + 1);
        break;
    case WARRIOR_TYPE.HT_BOX:
        cv1 = gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 1]; 
        cv2 = gameState.board[hero.top + dir[1] + 1][hero.left + dir[0] + 2];
        cv3 = gameState.board[hero.top + dir[1] + 2][hero.left + dir[0] + 1]; 
        cv4 = gameState.board[hero.top + dir[1] + 2][hero.left + dir[0] + 2];
        canMove = (cv1 == BOARD_CELL_EMPTY || cv1 == heroIdx + 1) && (cv2 == BOARD_CELL_EMPTY || cv2 == heroIdx + 1) 
            && (cv3 == BOARD_CELL_EMPTY || cv3 == heroIdx + 1) && (cv4 == BOARD_CELL_EMPTY || cv4 == heroIdx + 1);
        break;
    default:
        canMove = false;
        break;
    }

    return canMove;
}

function isEscaped(game, gameState){
    return (gameState.heroes[game.caoIdx -1].left == CAO_ESCAPE_LEFT) && (gameState.heroes[game.caoIdx - 1].top == CAO_ESCAPE_TOP)
}

function getZobristHash(zobHash, state)
{
    let hash = 0;
    let heroes = state.heroes;
    for(let i = 1; i <= HRD_GAME_ROW; i++) 
    {
        for(let j = 1; j <= HRD_GAME_COL; j++) 
        {
            let index = state.board[i][j] - 1;
            let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;
            hash ^= zobHash.get(i - 1,j - 1,type);
            // console.log(index+'--'+type+'--'+zobHash[i - 1][j - 1][type]+'<=>'+hash)
        }
    }
    return hash;
}

function getMirrorZobristHash(zobHash, state)
{
    let hash = 0;
    let heroes = state.heroes;
    for(let i = 1; i <= HRD_GAME_ROW; i++) 
    {
        for(let j = 1; j <= HRD_GAME_COL; j++) 
        {
            let index = state.board[i][j] - 1;
            let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;
            //(HRD_GAME_COL - 1) - (j - 1))
            hash ^= zobHash.get(i - 1,HRD_GAME_COL - j,type);
        }
    }
    return hash;
}

function addGameStateHero(gameState, heroIdx, hero)
{
    if(isPositionAvailable(gameState, hero.type, hero.left, hero.top))
    {
        takePosition(gameState, heroIdx, hero.type, hero.left, hero.top);
        gameState.heroes.push(hero);
        return true;
    }

    return false;
}

function clearPosition(gameState, type, left, top)
{
    switch(type)
    {
    case WARRIOR_TYPE.HT_BLOCK:
        gameState.board[top + 1][left + 1] = BOARD_CELL_EMPTY;
        break;
    case WARRIOR_TYPE.HT_VBAR:
        gameState.board[top + 1][left + 1] = BOARD_CELL_EMPTY;
        gameState.board[top + 2][left + 1] = BOARD_CELL_EMPTY;
        break;
    case WARRIOR_TYPE.HT_HBAR:
        gameState.board[top + 1][left + 1] = BOARD_CELL_EMPTY;
        gameState.board[top + 1][left + 2] = BOARD_CELL_EMPTY;
        break;
    case WARRIOR_TYPE.HT_BOX:
        gameState.board[top + 1][left + 1] = BOARD_CELL_EMPTY;
        gameState.board[top + 1][left + 2] = BOARD_CELL_EMPTY;
        gameState.board[top + 2][left + 1] = BOARD_CELL_EMPTY;
        gameState.board[top + 2][left + 2] = BOARD_CELL_EMPTY;
        break;
    default:
        break;
    }
}

function isPositionAvailable(gameState, type, left, top)
{
    let isOK = false;

    switch(type)
    {
    case WARRIOR_TYPE.HT_BLOCK:
        isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY);
        break;
    case WARRIOR_TYPE.HT_VBAR:
        isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY)
               && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY);
        break;
    case WARRIOR_TYPE.HT_HBAR:
        isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY)
               && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY);
        break;
    case WARRIOR_TYPE.HT_BOX:
        isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY)
               && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY)
               && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY)
               && (gameState.board[top + 2][left + 2] == BOARD_CELL_EMPTY);
        break;
    default:
        isOK = false;
        break;
    }

    return isOK;
}

function takePosition(gameState, heroIdx, type, left, top)
{
    switch(type)
    {
    case WARRIOR_TYPE.HT_BLOCK:
        gameState.board[top + 1][left + 1] = heroIdx + 1;
        break;
    case WARRIOR_TYPE.HT_VBAR:
        gameState.board[top + 1][left + 1] = heroIdx + 1;
        gameState.board[top + 2][left + 1] = heroIdx + 1;
        break;
    case WARRIOR_TYPE.HT_HBAR:
        gameState.board[top + 1][left + 1] = heroIdx + 1;
        gameState.board[top + 1][left + 2] = heroIdx + 1;
        break;
    case WARRIOR_TYPE.HT_BOX:
        gameState.board[top + 1][left + 1] = heroIdx + 1;
        gameState.board[top + 1][left + 2] = heroIdx + 1;
        gameState.board[top + 2][left + 1] = heroIdx + 1;
        gameState.board[top + 2][left + 2] = heroIdx + 1;
        break;
    default:
        break;
    }
}

var gameState = new HrdGameState()
var gameStateL = new HrdGameState()
var gameStateR = new HrdGameState()

var hs = [new Warrior(WARRIOR_TYPE.HT_BLOCK,0,0),          //构建武将列表，初始棋局
          new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,3,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,1),
          new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,1),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]
var hs2 = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
          new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,0,2),
          new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,3,2),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]
var hsl = [ new Warrior(WARRIOR_TYPE.HT_BOX,0,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,2,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
            new Warrior(WARRIOR_TYPE.HT_HBAR,0,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,2),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
            new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,4),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]
var hsr = [ new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,1,0),
            new Warrior(WARRIOR_TYPE.HT_BOX,2,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,2),
            new Warrior(WARRIOR_TYPE.HT_HBAR,2,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,4)
]
// gameState.initState(hs)
// console.dir(gameState.board)
// gameStateL.initState(hsl)
// gameStateR.initState(hsr)
// console.dir(getZobristHash(zobHash,gameStateL) + '--' + getMirrorZobristHash(zobHash,gameStateR))
//
// console.log(canHeroMove(gameState,6,1))
//
var gm = new HrdGame(2,hs)           //test move and move continue
var st = gm.states[0]
console.dir(st.board)
// var newSt = moveHeroToNewState(st,7,2)
// console.dir(newSt.board)
// addNewStatePattern(gm,newSt)
// tryHeroContinueMove(gm,newSt,7,2)
// console.dir(gm.states[2].board)

resolveGame(gm)
